Wiggle sort

Time: O(N); Space: O(1); medium

Given an unsorted array of nums, reorder it in-place such that: nums[0] <= nums[1] >= nums[2] <= nums[3]…

Example 1:

Input: nums = [3, 5, 2, 1, 6, 4]

Output: [3, 5, 1, 6, 2, 4] or [1, 6, 2, 5, 3, 4]

Explanation:

  • The pattern is number in odd position is peak.

  • First try to solve it without in-place:

    1. sort the array in increasing order.

    2. create a result array of the same size.

    3. keep 2 pointers, one from the beginning, one from the middle(notice odd/even of array).

    4. put beginning first, then the middle pointer, into the result array.

Note:

  • Solve it in-place.

[1]:

class Solution1(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums) < 2:
            return

        for i in range(1, len(nums)):
            if ((i % 2) and nums[i] < nums[i - 1]) or \
           (not (i % 2) and nums[i] > nums[i - 1]):
                # Swap unordered elements
                nums[i - 1], nums[i] = nums[i], nums[i - 1]

[2]:

s = Solution1()
nums = [3, 5, 2, 1, 6, 4]
s.wiggleSort(nums)
assert nums == [3, 5, 1, 6, 2, 4] or [1, 6, 2, 5, 3, 4]